package DynamicProgramming;
/*
 * 判断子序列
 */
public class lc392 {

    public boolean isSubsequence(String s, String t) {
        char[] S = s.toCharArray();
        char[] T = t.toCharArray();
        int lens = S.length;
        int lent = T.length;
        int[][] dp = new int[lens + 1][lent + 1];
        int res = 0;
        for (int i = 1; i < lens + 1; i++) {
            for (int j = 1; j <= lent; j++) {
                if (S[i - 1] == T[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res == lens;
    }

}
